package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/14 23:42
 * todo: 背包问题
 */
public class SnackWays {
    /**
     * 最简单的背包问题：给定一个weight重量的袋子，从arr里挑出几个能小于等于weight有几种方案
     */
    public int snackWays(int []arr,int weight){
        return process(arr,0,weight);
    }
    private int process(int[] arr,int index,int weight){
        if (weight < 0){
            return -1;
        }
        if (index == arr.length){
            return 1;
        }
        //不要当前元素
        int num1 = process(arr,index+1,weight);
        //要当前元素
        int num2 = process(arr,index+1,weight-arr[index]);
        return num1+(num2==-1?0:num2);
    }

    /**
     * 改造递归函数为dp
     */
    public int snackWaysWithDP(int []arr,int weight){
        if (arr == null || arr.length == 0 || weight < 0){
            return 0;
        }
        //首先声明一个二维数组，列的长度为容量大小，行的长度为数组的长度
        // 列的范围 ： [0~weight]
        // 行的范围 ： [0~arr.length]
        int dp[][] = new int[arr.length+1][weight+1];
        //先填基本数据，看递归基本数据是 最后一行的数据
        for (int i=0;i<dp[arr.length].length;i++){
            dp[arr.length][i] = 1;
        }
        for (int i=arr.length-1;i>=0;i--){
            for (int j=0;j<weight+1;j++){
                dp[i][j] = dp[i+1][j];
                if (j-arr[i]>=0){
                    dp[i][j] += dp[i+1][j-arr[i]];
                }
            }
        }
        return dp[0][weight];
    }

    /**
     * 将上面的DP进行空间压缩
     */
    public int snackWaysWithDPPushSpace(int []arr,int weight){
        if (arr == null || arr.length == 0 || weight < 0){
            return 0;
        }
        int dp[] = new int[weight+1];
        for (int i=0;i<weight+1;i++){
            dp[i] = 1;
        }
        for (int i=arr.length-1;i>=0;i--){
            for (int j=weight;j>=0;j--){
                dp[j] = dp[j] + (j-arr[i]>=0?dp[j-arr[i]]:0);
            }
        }
        return dp[weight];
    }

    public static void main(String[] args) {
        int []arr = {3,2,5,7};
        int weight = 10;
        SnackWays demo = new SnackWays();
        System.out.println(demo.snackWays(arr,weight));
        System.out.println(demo.snackWaysWithDP(arr,weight));
        System.out.println(demo.snackWaysWithDPPushSpace(arr,weight));
    }
}
